As part of a network, a routing device (a “router”) may be deployed in the network in order to forward data from its source to its desired destination. For example, as part of the Internet, routers are deployed which can receive data packets formatted according to the Internet Protocol (IP)—and therefore having a destination “IP address”—and forward those data packets to a network device connected to the router, which may be a device that either has the destination IP address as its address, or has a different IP address but will be able to forward the data packet through the network to reach the network device that has the destination IP address (i.e., another router or host computer connected to the network).
The process of routing is typically performed by accessing a “routing table,” which contains entries that indicate how to treat a data packet having a particular destination address. The routing table can be constructed in a number of different ways by routing protocols. One common method uses the “Open Shortest Path First” (OSPF) protocol, which is one of the two standard routing protocols for IP, specified in RFC 1247 (and updated in RFC 1583, RFC 2178 and RFC 2328). As part of the OSPF protocol, each router receives communications from other routers to which it is connected (“link state advertisements”), indicating those IP addresses to which they can provide routes, as well as “cost” information for using those routes. The OSPF protocol is then able to generate entries for the routing table which will allow forwarding of data packets using the fastest transmission path available.
An example routing table constructed using the OSPF protocol is illustrated in FIG. 1. Each table entry includes a destination IP address (or address range, if a subnet mask is specified), a routing path (e.g., the next router to forward to), and a transmission cost value (as well as other fields omitted for purposes of clarity). When a data packet is received by the router, the router compares the destination IP address provided in the data packet to the entries in the routing table, determines which entry most appropriately applies to the data packet, and forwards the packet via the routing path.
Recent developments in the IP protocol have led to the promulgation of a new version of the protocol named “IPv6,” and referenced in RFC 2460. The previous version of the IP protocol—named “IPv4”—used a 32-bit (4 byte) IP address format, sometimes presented in “dotted decimal” notation as “x.x.x.x” where each “x” is one byte of the address represented as a decimal number (e.g., “10.34.127.160”). (For additional information on IPv4 addressing, see RFC 791.) With the growth of the Internet, this addressing scheme has become too restrictive, as there is no longer a sufficient number of IPv4 addresses available, and therefore as part of IPv6, IP addresses take a 128-bit (16 byte) address format. These addresses are sometimes presented in hexadecimal notation as “xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx” where each “x” represents a hexadecimal digit and each grouping of four digits represents 2 bytes (e.g., “0000:FFE0:0000:0003:FFFF:FFFF:FFFC:00FD”). (See, for example, RFC 2373 and RFC 3513, for additional textual presentation formats.)
Although the IPv6 addressing scheme alleviates some of the addressing limitations of IPv4, it raises new problems for network devices in its implementation and deployment. For a certain transition period, both IPv4- and IPv6-capable devices will exist on the Internet. In order to access those devices configured for IPv4 addresses, a simple conversion was established—the first 12 bytes of an IPv4 address represented in IPv6 format are set to 0, and the last 4 bytes contain the IPv4 address. These are called IPv4 compatible IPv6 addresses. The IPv6 protocol functionality may be configured to recognize the IPv4 address embedded in the IPv6 address format, and provide the data packet to the appropriate processing modules for IPv4-addressed network traffic.
Another issue raised by the IPv6 addressing scheme is that the amount of memory needed to implement a routing table in a router expands by a significant amount from its implementation under IPv4. For example, each entry in an OSPF routing table compatible with IPv6 will include a 16-byte IPv6 destination address, whereas similar entries in an OSPF routing table under IPv4 would use 4 bytes for the destination IP address. In certain circumstances, adding additional memory to support routing table expansion is undesirable (e.g., too costly) or impossible (e.g., a previously built device being upgraded to IPv6 functionality).
Another issue raised by IPv6 addressing is additional computational cost in routing. In order to determine the appropriate forwarding route for a data packet received by a router, the router must compare the destination IP address in the data packet to entries in the routing table. With IPv4 addresses, this comparison was at most a 4 byte comparison, but with IPv6 this comparison can be up to a 16 byte comparison.